package recursionToDP;
/**
 * 如果一般情况下能 写出 记忆化 搜索的 版本  就可以 了 因为经典过程 和 记忆化搜索的 时间复杂度 是一样的 
 * 但是 如 果 AC 不掉 那就 再去 改动态规划 
 * 
 * 
 * 动态规划 用空间  换取时间  通过 这个 斐波那契 数列 我 悟了 一些东西
 * 缓存表  的维度 只与 暴力递归 的 可变参数 有关 有两个 可变参数  就是 二维表 三个 可变参数 就是三维 表 
 * 
 * 不是所有的 暴力递归 都可以 改成 动态规划  二是 所有的  动态规划 都来自 与 对应的 暴力递归
 * 没有重复过程的 暴力递归 就没必要 改  成动态规划
 * 可变参数的 结构化缓存
 * 状态转移 :  由已知  怎么 去求未知  的过程
 * 暴力递归 的 尝试 过程 就是 状态转移
 *
 * 暴力递归 中 return  的 在 动态规划 中 就是 设置 dp表的 值 的时候 
 * 常见的 四种 尝试模型 
 * 1.从左向右  尝试
 * 2.范围上尝试  
 * 3.多样本位置全 对应的 尝试 模型
 * 4.寻找业务限制的 尝试模型 
 * 
 * 
 * 
 * 
 * @author I adore you
 * 1.斐波那契数列
 * 
 * 
 * 
 * 2.机器人  走路 方式
 * 从顶向下 的  动态规划  又叫 记忆化 搜索 
 * 3. 玩牌 找最大分数 问题  ( 动态规划.博弈论 的  问题)
 * 4. 背包问题
 * 
 * 
 * 5.求两个字符串的 最长子序列问题（多样本 位置全对应的 尝试 模型）
 * 
 * 
 * 6.还有一个 很  类似于 回溯算法 解决的 那个题
 */
public class DP {
	static int a;
	static int b;
	public static void main(String []args) {
//		System.out.println(fabio1(7));
//		System.out.println(fabio2(7));
//		System.out.println(fabio3(7));
		System.out.println(walkWay(3,6,3,4));
		System.out.println(walkWay1(3,6,3,4));
		System.out.println(walkWay2(3,6,3,4));
		System.out.println(backTracing(3,6,4,3));
		//  想一下 什么时候 用加 for 什么时候 不用加 for
		System.out.println(a);
		System.out.println(b);
//		System.out.println(backTracing(3,6,4,3));

	}
	//  左  面试facebook  原题
	//这怎么改  能力有限 改不成 回溯 ？？
	public static int backing(char [] str,int index) {
		if(index == str.length) {
			return 1;
		}
		if(str[index]=='0') {
			return 0;
		}
		if(str[index]=='1') {
			int res=backing(str,index+1);
			if(index+1<str.length) {
				res+=backing(str,index+2);
			}
			return res;
		}
		if(str[index] == '2') {
			int res= backing(str,index+1);
			if(index + 1< str.length  && (str[index+1] >='0' && str[index+1]<='6')) {
				res+=backing(str,index+2); 
			}
			return res;
		}
		return backing(str,index+1);
		
//		for(int ) {
//			
//		}
	}
	//  斐波那契 数列问题  改成动态规划 的 尝试
	//  先写 暴力递归的 尝试
	public static int fabio1(int n) {
		if(n<1) {
			return -1;
		}
		return process1(n);
	}
	public static int  process1(int n) {
		if(n==0) {
			return 0;
		}
		if(n==1) {
			return 1;
		}
		if(n==2) {
			return 1;
		}
		return process1(n-1)+process1(n-2);
	}
	// 记忆化搜索的改写
	public static int fabio2(int n) {
		int dp[] =new int [n+1];
		//上面这个表是根据 递归中的  可变参数 决定的
		dp[1]=1;
		dp[2]=1;
		return process2(n,dp);
		
	}
	public static int process2(int n,int []dp) {
		if(n==0)
			return 0;
		if(n==1 ||n==2) {
			return dp[n];
		}
		dp[n]=process2(n-1,dp)+process2(n-2,dp);
		return dp[n];
	}
	public static int fabio3(int n) {
		int dp[] =new int [n+1];
		//每一次 dp 表 填值的 时候 都是对应着 原暴力递归的 中的每个 return 
		dp[1]=1;
		dp[2]=1;
		for(int i=3;i<=n;i++) {
			// 每一次 dp 表 填值的 时候 都是对应着 原暴力递归的 中的每个 return 
			dp[i]=dp[i-1]+dp[i-2];
		}
		return dp[n];
	}
	
	
	
	//2.机器人问题 
	//  试着 用 回溯 来写 一下    这里 明显 可以减少一个参数 得  rest 直接代替 target 和sum 
	//  这种 替换 就很  巧妙 因为 rest 另一个 边界  就已经限制了对吧  就是 0 ~ target; 这样的额话  就是可以 用一个
//	public static int backTracing(int cur,int target,int sum,int n,int aim) {
//		if(cur == target) {
//			return  sum == target ? 1 : 0;
//		}
//		
//	}
	/*
	 下面这个代码 是错误的！
	 当前 层 递归的选择 ，就两个， 没有必要 用 for 循环的！
	 */
	public static int backTracing(int cur,int rest ,int n,int aim) {
	    a++;
		if(rest == 0) {
			return  cur == aim ? 1 : 0;
		}
		if(cur == 1) {
			return backTracing(cur+1,rest-1,n,aim);
		}
		if(cur == n) {
			return backTracing(cur-1,rest-1,n,aim);
		}
		int ans=0;
		for(int i= cur; i< n;i++) {
			ans += backTracing(i+1,rest-1,n,aim) + backTracing(i-1,rest-1,n,aim);
		}
		return ans;
	}

	public static int walkWay(int start,int k,int aim,int n) {
		return process1(start,k,aim,n);
	}
	public  static int  process1(int cur,int rest,int aim,int n) {
		b++;
		if(rest==0) {
		//	base  case            key
			return cur==aim ? 1:0;
		}
		if(cur==1) {
			return process1(2,rest-1,aim,n);
//			return 0;
		}
		if(cur==n) {
//			return 0;
			return process1(n-1,rest-1,aim,n);
		}
		return process1(cur-1,rest-1,aim,n) +process1(cur+1,rest-1,aim,n);
	}
	
	// 优化 版本  记忆化 搜索过程 dp
	public static int walkWay1(int start,int k,int aim,int n) {
		// 制作一个 记忆表 就是缓存表  就是记忆探索过的 位置 就不用 看了   直接取值 
	   // cur=(1~n)
		//rest=(0~k) k 是总共要走的 步数
		// 为啥 初始化  为-1; 默认值 是 零 因为 方法  数 可能是0  这样就冲突 了没法算
		int [][]dp=new int[n+1][k+1];
		for(int i=0;i<=n;i++) {
			for(int j=0;j<=k;j++) {
				dp[i][j]=-1;
			}
		}
		process1(start,k,aim,n,dp);
		return dp[start][k];
	}
	public static int process1(int cur,int rest,int aim,int n,int [][]dp) {
		if(dp[cur][rest]!=-1) {
			//basecase  就是 之前算过 直接 取值 不算了
			return dp[cur][rest];
		}
		// 这说明之前 没算过 ;
		// 这里有个 小小的  疑惑点  就是 这个ans 这个东西 
		//只有 没有 走 的路 才会 进行下面这些过程   没有做过的  话 先假设 结果为  0  很合理 这里不要迷 
		int ans=0;
		if(rest==0) {
			ans= cur==aim ? 1:0;
		}
		else if(cur==1) {
			ans= process1(2,rest-1,aim,n,dp);
		}
		else if(cur==n) {
			ans= process1(n-1,rest-1,aim,n,dp);
		}
		else {
			ans=process1(cur+1,rest-1,aim,n,dp)+process1(cur-1,rest-1,aim,n,dp);
		}
		dp[cur][rest]=ans;
		return ans;
		
	}
	// 最终版本的 dp 终于出来 了 下面 就是 动态规划 
	public static int walkWay2(int start,int k,int aim,int n) {
		//  默认值 是零 0   
		int [][]dp=  new  int [n+1][k+1];
		//  注意 这里 为啥 不用初始化 为-1;
		//  因为这里 数组里面的 0 没有影响 这是 直接 根据 状态转移方程 来算这个题 
		dp[aim][0]=1;
		//  上面  的 代码 相当于 第零 0列 已经搞定了  所以 坑定 按 列 来填表啊  按行咋狗吧 填?
//		for(int i=1;i<=n;i++) {
//			dp[1][rest]=dp[2][rest-1];
//			for(int )
		for(int j=1;j<=k;j++) {
			dp[1][j]=dp[2][j-1];
			for(int i=2; i< n ;i++) {
				dp[i][j] = dp[i+1][j-1] + dp[i-1][j-1];
			}
			dp[n][j] = dp[n-1][j-1];
		}
		return dp[start][k];
	}
	
}
